/**
 * 构建二叉树
 * （中序遍历可以提供关于根节点在左右子树中的位置的信息）
 * 前序+中序
 * 后序+中序
 * 层序
 */
import levelOrder from './0-层序遍历.js'
const preOrderList = [1, 2, 4, 5, 3];
const inOrderList = [4, 2, 5, 1, 3];
const postOrderList = [4, 5, 2, 3, 1];
const levelOrderList = [1, 2, 3, 4, 5];

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

/**
 * 根据 前序+中序 构建二叉树
 */
var buildTree = function(preorder, inorder) {
  if (!preorder.length) return null;
  const rootVal = preorder.shift(); // 从前序遍历的数组中获取中间节点的值， 即数组第一个值
  const index = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
  const root = new TreeNode(rootVal); // 创建中间节点
  root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index)); // 创建左节点
  root.right = buildTree(preorder.slice(index), inorder.slice(index + 1)); // 创建右节点
  return root;
}
const root = buildTree(preOrderList,inOrderList)
console.log('前序+中序',levelOrder(root))
/**
 * 根据 后序+中序 构建二叉树 后序的最后一个节点是根节点
 */
function buildTree2(inorder,postorder) {
  if (!inorder.length) return null;
  const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
  const index = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标
  
  const root = new TreeNode(rootVal); // 创建中间节点
  root.left = buildTree2(inorder.slice(0, index), postorder.slice(0, index)); // 创建左节点
  root.right = buildTree2(inorder.slice(index+1), postorder.slice(index)); // 创建右节点
  return root;
}
const root2 = buildTree2(inOrderList,postOrderList)
console.log('后序+中序',levelOrder(root2))

